package airthmetic.exercise.backtrack;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class _46_全排列 {
    public List<List<Integer>> permute(int[] nums) {
        // 已经记录的组合
        // 已经走过的路径(已经做过的决策)
        // 剩余可选的列表
        // 结束条件
        boolean[] selected = new boolean[nums.length];
        Deque<Integer> queue = new LinkedList();
        List<List<Integer>> res = new ArrayList();

        recur(1,nums,selected,queue,res);
        return res;

    }


    public void recur(int level, int[] nums, boolean[] selected, Deque<Integer> queue, List<List<Integer>> res){
        // terminal
        if(level > nums.length){
            res.add(new ArrayList(queue));
            return;
        }

        for(int i=0; i< nums.length; i++){
            // process current logic
            if(!selected[i]){
                queue.addLast(nums[i]);
                selected[i] = true;
                // drill down
                recur(level + 1, nums, selected,queue,res);

                // 回溯
                queue.removeLast();
                selected[i] = false;
            }
        }



    }
}
